package com.techyuan.algorithm.sorts.other;

/**
 * 最大优先队列，使用堆排序思想实现
 * @author derek.tian on 2016/11/27.
 */
public class PriorityQueue {
    private int heapSize;
    private Node[] heap;

    public PriorityQueue() {
        heap = new Node[100];//固定队列大小，弱化扩容问题。
        heapSize = 0;
    }

    public Object front() {
        if (heapSize < 1)
            throw new RuntimeException("堆异常");

        return heap[0].getObj();
    }

    public Object pop() {
        if (heapSize < 1)
            throw new RuntimeException("堆异常");

        Node max = heap[0];
        heap[0] = heap[heapSize - 1];
        heapSize = heapSize - 1;
        maxHeapify(heap, heapSize, 1);
        return max.getObj();
    }

    public void changePriority(Object obj, int priority) {
        int objIndex = -1;
        for (int i = 0; i < heapSize; i++) {
            if (heap[i].getObj() == obj) {
                objIndex = i + 1;
                break;
            }
        }

        if (priority < heap[objIndex - 1].getPriority())
            throw new RuntimeException("堆异常");

        heap[objIndex - 1].setPriority(priority);
        while (objIndex > 1 && heap[getParentIndex(objIndex) - 1].getPriority() < heap[objIndex - 1].getPriority()) {
            swap(heap, objIndex, getParentIndex(objIndex));
            objIndex = getParentIndex(objIndex);
        }
    }


    public void push(int priority, Object obj) {
        heapSize = heapSize + 1;
        heap[heapSize - 1] = new Node(Integer.MIN_VALUE, obj);
        changePriority(obj, priority);
    }

    /**
     * 维护最大堆
     *
     * @param sortArr
     * @param i
     */
    public void maxHeapify(Node[] sortArr, int heapSize, Integer i) {
        int largest;
        int l = getLeftIndex(i);
        int r = getRightndex(i);
        if (l <= heapSize && sortArr[l - 1].getPriority() > sortArr[i - 1].getPriority())
            largest = l;
        else
            largest = i;
        if (r <= heapSize && sortArr[r - 1].getPriority() > sortArr[largest - 1].getPriority())
            largest = r;
        if (largest != i) {
            swap(sortArr, i, largest);
            maxHeapify(sortArr, heapSize, largest);
        }
    }

    public void buildMaxHeap(Node[] sortArr) {
        int heapSize = sortArr.length;
        for (int i = (int) Math.floor(heapSize / 2); i > 0; i--) {
            maxHeapify(sortArr, heapSize, i);
        }
    }

    public void heapSort(Node[] sortArr) {
        buildMaxHeap(sortArr);
        int heapSize = sortArr.length;
        for (int i = heapSize; i > 1; i--) {
            swap(sortArr, 1, i);
            heapSize = heapSize - 1;
            maxHeapify(sortArr, heapSize, 1);
        }
    }

    private void swap(Node[] arr, int i, int j) {
        Node tmp = arr[i - 1];
        arr[i - 1] = arr[j - 1];
        arr[j - 1] = tmp;
    }

    private int getParentIndex(int index) {
        return index >> 1;
    }

    private int getLeftIndex(int index) {
        return index << 1;
    }

    private int getRightndex(int index) {
        return (index << 1) + 1;
    }

    private class Node {
        private int priority;
        private Object obj;

        private Node(int p, Object o) {
            this.priority = p;
            this.obj = o;
        }

        public int getPriority() {
            return priority;
        }

        public void setPriority(int priority) {
            this.priority = priority;
        }

        public Object getObj() {
            return obj;
        }

        public void setObj(Object obj) {
            this.obj = obj;
        }
    }

    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue();
        queue.push(5, "节点值：5");
        queue.push(8, "节点值：8");
        queue.push(2, "节点值：2");
        queue.push(1, "节点值：1");
        queue.push(7, "节点值：7");

        for (int i = 0; i < 5; i++) {
            Object obj = queue.pop();
            System.out.println(obj);
        }
    }
}
